#include <iostream>
#include <unordered_map>

using namespace std;
// 思路： 使用双向链表和哈希表实现LRU缓存
struct node
{
    int key;
    int value;
    node *next;
    node *prev;
    node(int k, int v)
    {
        key = k;
        value = v;
        next = nullptr;
        prev = nullptr;
    }
};
class LRUCache
{
public:
    node *head;                       // 哨兵节点
    node *tail;                       // 哨兵节点
    int cap;                          // 容量
    unordered_map<int, node *> u_map; // 哈希表存储key和节点的映射

public:
    LRUCache(int capacity) // 构造函数
    {
        cap = capacity;
        head = new node(0, 0); // 创建哨兵节点
        tail = new node(0, 0); // 创建哨兵节点
        head->next = tail;     // 连接哨兵节点
        head->prev = tail;
        tail->next = head;
        tail->prev = head;
    }

    int get(int key)
    {
        // 如果存在则将节点移动到头部并返回值，否则返回-1
        if (u_map.count(key))
        {
            remove(u_map[key]);       // 移除节点
            headinsert(u_map[key]);   // 插入到头部
            return u_map[key]->value; // 返回值
        }
        return -1;
    }

    void put(int key, int value)
    {
        // 1. 如果存在则更新值并将节点移动到头部
        if (u_map.count(key))
        {
            remove(u_map[key]);
            delete u_map[key];
        }
        // 2. 如果不存在则创建新节点并插入到头部
        node *temp = new node(key, value);
        headinsert(temp);
        u_map[key] = temp;
        // 3. 如果超过容量则删除尾部节点
        if (u_map.size() > cap)
        {
            node *todel = tail->prev;
            remove(todel);
            u_map.erase(todel->key);
            delete todel;
        }
    }
    void remove(node *temp)
    {
        node *next = temp->next;
        node *prev = temp->prev;
        prev->next = next;
        next->prev = prev;
    }
    void headinsert(node *temp)
    {
        node *nxt = head->next;
        head->next = temp;
        temp->prev = head;
        temp->next = nxt;
        nxt->prev = temp;
    }
};
